/*
 * @Descripttion:
 * @version:
 * @Author: xiaozilai
 * @Date: 2022-10-31 15:37:52
 * @LastEditors: xiaozilai
 * @LastEditTime: 2022-10-31 16:08:14
 */
/*
 * @lc app=leetcode.cn id=481 lang=cpp
 *
 * [481] 神奇字符串
 *
 * https://leetcode.cn/problems/magical-string/description/
 *
 * algorithms
 * Medium (57.85%)
 * Likes:    130
 * Dislikes: 0
 * Total Accepted:    22.6K
 * Total Submissions: 35.3K
 * Testcase Example:  '6'
 *
 * 神奇字符串 s 仅由 '1' 和 '2' 组成，并需要遵守下面的规则：
 *
 *
 * 神奇字符串 s 的神奇之处在于，串联字符串中 '1' 和 '2' 的连续出现次数可以生成该字符串。
 *
 *
 * s 的前几个元素是 s = "1221121221221121122……" 。如果将 s 中连续的若干 1 和 2 进行分组，可以得到 "1 22 11
 * 2 1 22 1 22 11 2 11 22 ......" 。每组中 1 或者 2 的出现次数分别是 "1 2 2 1 1 2 1 2 2 1 2 2
 * ......" 。上面的出现次数正是 s 自身。
 *
 * 给你一个整数 n ，返回在神奇字符串 s 的前 n 个数字中 1 的数目。
 *
 *
 *
 * 示例 1：
 *
 *
 * 输入：n = 6
 * 输出：3
 * 解释：神奇字符串 s 的前 6 个元素是 “122112”，它包含三个 1，因此返回 3 。
 *
 *
 * 示例 2：
 *
 *
 * 输入：n = 1
 * 输出：1
 *
 *
 *
 *
 * 提示：
 *
 *
 * 1 <= n <= 10^5
 *
 *
 */

// @lc code=start
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
    int magicalString(int n) {
        string original_s{"122"};
        string freq_s{"122"};
        string temp{"2"};
        helper(original_s, freq_s, temp, n);
        cout << original_s << endl;
        int ans = 0;
        for (auto &letter : original_s) {
            if (letter == '1') {
                ++ans;
            }
        }
        return ans;
    }

    void helper(string &original_s, string &freq_s, string &temp, int n) {
        if (!temp.empty()) {
            for (auto &item : temp) {
                if (item == '1') {
                    original_s += (original_s.back() == '1' ? "2" : "1");
                } else {
                    original_s += (original_s.back() == '1' ? "22" : "11");
                }
            }
        }
        int length_1 = original_s.length();
        if (length_1 >= n) {
            original_s = original_s.substr(0, n);
            return;
        }
        int length_2 = freq_s.length();
        if (length_2 < length_1) {
            temp = original_s.substr(length_2);
        }
        freq_s += temp;
        helper(original_s, freq_s, temp, n);
    }
};
// @lc code=end
